﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Analysis_Sorting_Algorithms
{
    class HeapSort
    {
        public int[] sortIt(int[] array, ref int compare)
        {
            int length = array.Length;

            makeheap(array, length, ref compare);
            for (int i = length; i >= 2; i--)
            {
                swap(array, 1, i);          //swap first element and 
                length = length - 1;
                Heapify(array, 1, length, ref compare);
            }
            return array;
        }

        private void makeheap(int[] array, int length, ref int compare) // Book page 157
        {
            for (int i = length/2; i >= 1; i--)
                Heapify(array,i, length, ref compare);
        }

        private void Heapify(int[] array, int i, int length, ref int compare)    //Copied from book Page 154 (6.2)
        {
            int l = left(i);    //Gets Left Child
            int r = right(i);   //Gets Right Child
            int largest = i;    //Largest = i (parent) to start

            if (l <= length && array[l - 1] > array[i - 1])   //if L > Parent thn Largest = l
            {
                largest = l;                                        //if L > Largest set largest to l
                compare++;
            }
            if (r <= length && array[r - 1] > array[largest - 1]) // if array[r] > array[largest]
            {
                largest = r;                                        //set largest to r
                compare++;
            }
            if (largest != i)                                           // if parent is not largest
                {                                                       // swap parent and the largest
                    swap(array, i, largest);                            //
                    Heapify(array, largest, length, ref compare);
                    compare++;
                }
        }

        public int left(int i) //Pg 152
        {
            return 2 * i;
        }

        public int right(int i) //Pg 152
        {
            return 2 * i + 1;
        }
     
        public void swap(int[] array, int a, int b) //Swap the 2 ints in the array
        {
            int temp = array[a-1];
            array[a-1] = array[b-1];
            array[b-1] = temp;
            return;
        }
    }
}
